package leetcode.easy.q112;

import leetcode.util.TreeNode;
import lombok.extern.slf4j.Slf4j;

import static leetcode.util.Utils.buildTree;

@Slf4j
public class Q {
    public static void main(String[] args) {
        log.info("{}", new Solution().hasPathSum(buildTree(5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1), 22));
    }

}

/*
递归：只有叶子节点并且dff为0时说明match
 */
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;
        int diff = targetSum - root.val;
        if (isLeaf(root) && diff == 0) {
            return true;
        } else {
            return hasPathSum(root.left, diff) || hasPathSum(root.right, diff);
        }
    }

    private boolean isLeaf(TreeNode node) {
        return node.left == null && node.right == null;
    }
}